1. Field of the Invention
The present invention is directed to a method and apparatus for representing indexing information in a database, and more particularly to a method and system for representing indexing and query information using an interval hash tree to allow efficient query object localization.
2. Description of the Related Art
As image databases grow larger and larger in size, index structures for fast navigation become important. In particular, when the goal is to locate object queries in large image databases using their spatial layout information, traditional index structures used in databases such as B-tree, R-tree, R*-tree, etc., become unsuitable, especially, since the query object must be localized in the presence of pose changes, occlusions and spurious data in images.
More particularly, when the goal is to locate object queries in large image databases, it is desirable to avoid a detailed search of either the image database or the images themselves. This is due to several reasons.
First, without a perfect segmentation, it is not clear which collection of image regions comes from the query object without exploring multiple possibilities. This becomes very time-consuming, if not computationally prohibitive. This problem is made worse when changes in imaging conditions and pose changes alter the appearance of the object in images. Finally, occlusions and background clutter make it difficult to interpret partial object appearances. Robustly locating objects under these conditions requires efficient index structures that can consolidate pose-invariant information within and across images in a compact and efficiently searchable form. This problem is often recognized but has not been explicitly addressed prior to the present invention.
To illustrate the above problem, consider locating a query based on its spatial layout of regions. This requires modeling the layout of regions in images of the database, and representing the layout in a suitable index structure. The matching of the query regions then involves finding the best subset of image regions in the database that are likely to arise from the query object regions. Frequently, the information about the regions can be represented by suitable bounding boxes, which for scene regions are overlapping windows. Then, the query localization problem reduces to the problem of finding all the image database intervals that overlap with a set of query intervals.
An efficient data structure and algorithm for the solution to this problem is important not only in content-based retrieval of image databases, but also in a number of other applications such as map-based navigation systems, VLSI design and testing, and flight simulation.
For example, state-of-the-art cars are equipped with vehicle navigation systems that help the user determine his/her position and guide to the user to his/her destination. Such a system stores a whole roadmap of for example, the entire U.S. It also keeps track of where the user is, so that it can show the appropriate part of the roadmap at any time on a small computer screen. This will usually be a rectangular region around the user""s present position.
To be of any use, the map should contain sufficient detail. A detailed map, however, contains an enormous amount of data, not all of which can be displayed on the screen at one time. In that case, given a query region isolated by a user, the system must find that part of the map (roads, cities, and so on) that lie in the window, and display them. This will require finding all regions of the map represented by possibly overlapping bounding boxes that overlap with the query window(s). Checking every single feature of the map to see if it lies inside the query window is not feasible due to the amount of data.
Traditional index structures are insufficient for object localization under the above circumstances. That is, while these data structures do address the search aspect, most of the conventional indexing structures are focused on reducing the seek time on disk reads for secondary memory data storage, and the robust localization aspect has not been well-addressed.
For example, R-trees and their variants [Guttman, Proc. SIGMOD, 1984, pp. 47-57, Beckman et al., Proc. SIGMOD, 1990, pp. 322-331, Sellis, Roussopolous and Faloustous, VLDB 1987, pp. 507-519, Katayama and Satoh, SIGMOD 1997, pp. 369-380 White and Jain, Int. Conf. On Data Engg., 1996, pp. 516-523, Robinson, Proc. SIGMOD 1981, pp. 10-18] assume the object-containing region in the image can be enclosed by bounding rectangles and focus on efficient grouping of the enclosing rectangles at successive levels to yield a balanced search tree that is optimized for disk accesses. The search for object queries in such index structures involves finding all database rectangles that overlap a query rectangle. Under changes in pose, the bounding rectangles undergo considerable change including translation, so that the search using these index structures no longer yields a match to the query. Other search trees such as k-D trees are used more for point searches than rectangle searches. That is, the database access problem addressed using those trees is determining the set of database points that fall within a single query rectangle. There is also prior art in addressing the general rectangle intersection problem [Six-Wood, BIT, vol. 20, pp. 426-433, 1980] where the problem is to determine the set of intersecting rectangles in a n-D plane. Efficient implementation of the rectangle intersection algorithm also exploit the 1d-interval tree, a data structure proposed by Edelsbrunner [Edelsbrunner, Rep. F59, Tech. Univ. Graz, 1980]. This invention proposes a 2D extension to the interval tree proposed by Edelsbrunner.
Thus while representing rectangles in a conventional spatial access structure such as an R-tree is a possibility, unless the search for all query intervals can be consolidated, this would be inefficient. Another possibility is to use an index structure such as a multi-dimensional hash table as done in geometric hashing. However, these tables would require quantizing the space of rectangles into cells and recording the presence of intervals in each cell, an operation that would be computationally prohibitive, both in storage space and in search time during indexing. Finally, graph-like representations that capture the layout of query or database rectangles are not suitable either due to the complexity associated with sub-graph matching.
Thus, representing database intervals in a manner that avoids a repetitious search for query affine intervals can be a difficult problem. In fact, it turns out this is a well-known problem in computational geometry, an efficient solution of which is needed in several applications besides image databases, such as map-based navigation systems, VLSI design and testing, and flight simulation, as discussed above.
What is needed is a representation of overlapping window information in a suitable index structure which can also be quickly searched to retrieve the relevant intervals. Further, when there are multiple query intervals, it would be advantageous to consolidate the multiple searches so as to avoid repetition.
In view of the foregoing and other problems, disadvantages, and drawbacks of the conventional methods and structures, an object of the present invention is to provide a method and structure in which the above problems are solved.
In a first aspect of the present invention, a system and method for representing database information for multiple windows using a two-way interval tree called the interval hash tree is presented. A second aspect of the present invention is the notion of representing the query interval information also as an interval hash tree and matching the query interval tree nodes to the database interval tree nodes in a manner that avoids redundant exploration of nodes for overlapping query intervals.
Thus, with the unique and unobvious features of the present invention, a method and system are provided for supporting fast indexing of spatial layout queries. Moreover, the invention creates a novel data structure called the 2-way interval hash tree. The method of matching query and interval hash trees nodes for nodes is the first method that can find simultaneously the set of database windows that overlap a set of query windows without ever repeating the search for overlapping query windows. Finally, representing and indexing of overlapping database intervals allows a novel way of locating object queries that avoids repetitious search of the database, and has implications as a new addition to index structures available to spatial databases.